package solutions.leetcode.normal

import java.util.Arrays

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/arithmetic-subarrays/">1630. 等差子数组</a>
 */
private class Solution1630 {
    fun checkArithmeticSubarrays(nums: IntArray, l: IntArray, r: IntArray): List<Boolean> {
        val res = BooleanArray(l.size)
        for (i in l.indices) {
            var max = Int.MIN_VALUE
            var min = Int.MAX_VALUE
            for (ind in l[i] .. r[i]) {
                max = Math.max(max, nums[ind])
                min = Math.min(min, nums[ind])
            }
            if ((max - min) % (r[i] - l[i]) != 0) {
                continue
            }
            val step = (max - min) / (r[i] - l[i])
            if (step == 0) {
                res[i] = true
                continue
            }
            val flag = BooleanArray(r[i] - l[i] + 1)
            var ok = true
            for (ind in l[i] .. r[i]) {
                val offset = nums[ind] - min
                if (offset % step != 0 || flag[offset / step]) {
                    ok = false
                    break
                }
                flag[offset / step] = true
            }
            res[i] = ok
        }
        return res.toList()
    }
}

fun main() {
    println(
        Solution1630().checkArithmeticSubarrays(
            intArrayOf(
                -12,-9,-3,-12,-6,15,20,-25,-20,-15,-10
            ),
            intArrayOf(
                0,1,6,4,8,7
            ),
            intArrayOf(
                4,4,9,7,9,10
            )
        )
    )
}